package 牛客网在线编程题库;

import java.util.HashSet;

/**
 * 对于一个给定的链表，返回环的入口节点，如果没有环，返回null
 * 拓展：
 * 你能给出不利用额外空间的解法么？
 */

public class _链表中环的入口结点 {
    public static void main(String[] args) {

    }

    public static 牛客网在线编程题库.ListNode detectCycle(牛客网在线编程题库.ListNode head) {
        // 定义散列表存放结点
        HashSet<牛客网在线编程题库.ListNode> set = new HashSet<>();
        // 从当前结点开始遍历链表
        while (head != null) {
            // 若当前结点在散列表中
            if (set.contains(head)) {
                return head;
            }else {
                set.add(head);
            }
            head = head.next;
        }
        return null;
    }
}
